import java.util.Arrays;

/**
 * 未解决
 */

public class _天平砝码问题 {
    public static void main(String[] args) {
        // 砝码重量m
        int m = 6;
        // 物品数量n
        int n = 5;
        // 物品重量数组
        int[] w = {1, 3, 4, 7, 12};

        int target = balanceWeight1(m, n, w);
        System.out.println(target);
    }

    public static int balanceWeight1(int m, int n, int[] w) {
        // 定义最大的物品重量
        int max = w[0];
        // 挑选出最大的物品重量
        for (int i = 1 ; i < w.length ; i++) {
            if (w[i] > max) {
                max = w[i];
            }
        }
        // dp[i]表示重量为i所需要的最少物品数
        int[] dp = new int[max * m + 1];
        // 求最小，故全部填充为最大值
        Arrays.fill(dp, Integer.MAX_VALUE);
        // 重量为0，所需物品数自然也为0
        dp[0] = 0;
        // 遍历
        for (int i = 0 ; i < n ; i++) {
            for (int j = 1 ; j <= max * m ; j++) {
                // 如果砝码剩余的容量还能放入物品
                if (j - w[i] >= 0) {
                    // 寻找j-w[i]重量所需要的最少物品数，然后+1即为当前的最少物品数
                    dp[j] = Math.min(dp[j], dp[j - w[i]] + 1);
                }
            }
        }
        // 遍历m的倍数，查看所有可能的值
        for (int i = 1 ; i < dp.length ; i++) {
            if (i % m == 0) {
                System.out.print(dp[i] + ", ");
            }
        }
        return -1;
    }

    public static int balanceWeight(int m, int n, int[] w) {
        // 挑选出最大的物品重量
        int max = w[0];
        for (int i = 1 ; i < w.length ; i++) {
            if (w[i] > max) {
                max = w[i];
            }
        }
        // dp[i][j]表示使用i件商品，组成j重量需要的最少的物品数
        int[][] dp = new int[n + 1][max * m + 1];
        for (int i = 0 ; i <= n ; i++) {
            Arrays.fill(dp[i], Integer.MAX_VALUE);
        }
        // 初始化
        for (int i = 0 ; i <= n ; i++) {
            dp[i][0] = 1;
        }
        for (int i = 0 ; i <= max * m ; i++) {
            dp[0][i] = 0;
        }

        // 遍历
        for (int i = 1 ; i <= n ; i++) {
            for (int j = 1 ; j <= max * m ; j++) {
                if (j - w[i - 1] >= 0) {
                    dp[i][j] = dp[i - 1][j] + dp[i][j - w[i - 1]];
                }else {
                    dp[i][j] = dp[i - 1][j];
                }
            }
        }
        int min = Integer.MAX_VALUE;
        for (int i = 1 ; i <= n ; i++) {
            for (int j = 1 ; j <= max * m ; j++) {
                System.out.print(dp[i][j] + " ");
                if (i < min) {
                    min = i;
                }
            }
            System.out.println();
        }
        return min;
    }
}
